| |
| description |
24 pages
|
|
Relational division, also known as small divide, is a derived
operator of the relational algebra that realizes a many-to-one set
containment test, where a set is represented as a group of tuples:
Small divide discovers which sets in a dividend relation contain all
elements of the set stored in a divisor relation. The great divide
operator extends small divide by realizing many-to-many set
containment tests. It is also similar to the set containment join
operator for schemas that are not in first normal form. Neither
small nor great divide has been implemented in commercial relational
database systems although the operators solve important problems and
many efficient algorithms for them exist. We present algebraic laws
that allow rewriting expressions containing small or great divide,
illustrate their importance for query optimization, and discuss the
use of great divide for frequent itemset discovery, an important
data mining primitive. A recent theoretic result shows that small
divide must be implemented by special purpose algorithms and not be
simulated by pure relational algebra expressions to achieve
efficiency. Consequently, an efficient implementation requires that
the optimizer treats small divide as a first-class operator and
possesses powerful algebraic laws for query rewriting.
|
| publisher |
Stuttgart, Germany, Universität Stuttgart
|
| type |
Text
|
| Technical Report
|
| source |
ftp://ftp.informatik.uni-stuttgart.de/pub/library/ncstrl.ustuttgart_fi/TR-2005-08/TR-2005-08.pdf
|
| contributor |
IPVS, Anwendersoftware
|
| format |
application/pdf
|
| 342028 Bytes
|
| subject |
Database Management Systems (CR H.2.4)
|
| relation |
Technical Report No. 2005/08
|